/* 容斥原理
* 常见问题:
    (1)有n个相同的元素,要求分到m组中,每组至少元素数为1,问有多少种不同的分法？
    C(n-1, m-1)

    (2)允许有些组中分到的元素数为0，也就是组中可以为空的
    首先将每组都填上1个，这样所要元素总数就n+m个，问题也就是转变成将(n+m)个元素分到m组
    C(n+m-1, m-1)

* 莫比乌斯反演(Mobius)
    x = p1^a1 * p2^a2 * ... * pk^ak
                | 0, ai > 1
    Mobius(x) = | 1, k是偶数
                |-1，k是奇数
    
* 本题:
    1<=x<=a 1<=y<=b (x,y)==d
    -> 1<=x'<=(a/d) 1<=y'<=(b/d) (x',y')==1
    a'=(a/d) b'=(b/d)
    -> a'b' - (a'/2)(b'/2) - (a'/3)(b'/3) -...+(a'/6)(b'/6)+...
    -> a'b' + (累加1~min(a',b'))(a'/i)(b'/i)*Mobius[i]

    g[x]: g[x]最大取多少使a/x==a/g[x] 且(a/x) > (a/(g[x]+1))
*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define int long long
const int N = 5e4+10;

int primes[N], cnt;
bool st[N];
int mobius[N], sum[N]; //莫比乌斯数组 莫比乌斯前缀和数组

//线性筛法，求莫比乌斯函数
void init(int n)
{
    mobius[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])
        {
            primes[cnt++] = i;
            mobius[i] = -1;//i本身是质数
        }
        for(int j = 0; primes[j]*i <= n; j++)
        {
            int t = primes[j]*i;
            st[t] = true;
            if(i % primes[j] == 0)
            {
                mobius[t] = 0; //包含两个primes[j]
                break;
            }
            mobius[t] = mobius[i] * -1;//不能整除 
        }
    }
    for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + mobius[i];
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt", "r", stdin);
    #else
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    init(N-1);

    int T; cin >> T;
    while(T--)
    {
        int a, b, d; cin >> a >> b >> d;
        a /= d; b /= d; //计算a', b'
        int n = min(a, b);
        int res = 0;
        for(int l = 1, r; l <= n; l = r+1)
        {
            r = min(n, min(a/(a/l), b/(b/l)));//计算g[x] [l,r]内a/i,b/i值不变
            res += (sum[r] - sum[l-1]) * (a/l) * (b/l);
        }
        printf("%lld\n", res);
    }
    
    return 0;
}
